package com.algorithm.ch2.cjm.array;

/**
 * 最长回文子串
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 *
 * 示例1：
 * 输入："babad"
 * 输出："bab"
 * 注意："aba" 也是一个有效答案。
 *
 * 示例 2：
 * 输入: "cbbd"
 * 输出: "bb"
 *
 * @Author: Jie Ming Chen
 * @Date: 2019-03-20
 * @Version 1.0
 */
public class LongestPalindrome {

    /**
     * 最长公共子串
     *
     * S = "abacdfgdcaba"
     * S'= "abacdgfdcaba"
     *
     * S = "ggabccba"
     * S'= "abccbagg"
     *
     * @param s
     * @return
     */
    public String longestPalindrome1(String s) {
        StringBuilder s1 = new StringBuilder(s);
        s1.reverse();



        return null;
    }

    /**
     * 动态规划求解
     *
     * @param s
     * @return
     */
    public String longestPalindrome3(String s) {
        int n = s.length();
        String res = null;

        boolean[][] dp = new boolean[n][n];

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);

                if (dp[i][j] && (res == null || j - i + 1 > res.length())) {
                    res = s.substring(i, j + 1);
                }
            }
        }

        return res;
    }

    // 暴力法
    // 求出所有可能出现的子串的长度，然后验证是不是回文字符串
    // 时间复杂度O(n^3)
    public String longestPalindrome2(String s) {
        if (s.length() == 0) {
            return s;
        }
        int length = s.length();
        while (length > 0) {
            int x = 0;
            while (x <= s.length() - length) {
                String substring = s.substring(x, x + length);
                if (isPalindrome(substring)) {
                    return substring;
                }
                x++;
            }
            length--;
        }
        return null;
    }

    // 使用位图法 + 双指针法
    private boolean isPalindrome(String str) {
        char[] chars = str.toCharArray();
        int[] arr = new int[str.length()];

        int length = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == ' ') {
                continue;
            }
            int inta = chars[i] - 'a';
            int intA = chars[i] - 'A';
            if (chars[i] >= '0' && chars[i] <= '9') {
                arr[length++] = chars[i] - '0';
            } else if(inta >= 0 && inta <= 25) {
                arr[length++] = inta + 10;
            } else if (intA >= 0 && intA <= 25) {
                arr[length++] = intA + 10;
            }
        }

        int x = 0;
        int y = length - 1;
        while (x < y) {
            if (arr[x] != arr[y]) {
                return false;
            }
            x++;
            y--;
        }
        return true;
    }

    public static void main(String[] args) {
        long start = System.nanoTime();
        String abccba = new LongestPalindrome().longestPalindrome3("kxuuisplqldxxqanojzyqlaycqwwrpczkymlbpoolybkbluvfkxzzxsoulnfhlhlqzibfhnbryhbkauxsuavnuqlinxrfdwgypsgjmilygtsqptbmfibcfkgdugljwpzjmwnqhtadraplrtlcxeqoniopzbemhkezvadjblpgmyuwlkwilipuccuqfvyzxtoathpnprqphtsiqjlocrmupngjnuskvbzadwxtxchsutumbvidxauotploicaqxegkstdfkyqbmegjhzdrqsuvrspqzbesgzwelrlejlilqvybdjyflbcziqlncddoohurovyuhfhjoyrkxbrvsepxbsivtrahz");
        long end = System.nanoTime();
        System.out.println(abccba + "时间：" + (end - start) / (1000 * 1000));

        long start1 = System.nanoTime();
        String abccba1 = new LongestPalindrome().longestPalindrome2("kxuuisplqldxxqanojzyqlaycqwwrpczkymlbpoolybkbluvfkxzzxsoulnfhlhlqzibfhnbryhbkauxsuavnuqlinxrfdwgypsgjmilygtsqptbmfibcfkgdugljwpzjmwnqhtadraplrtlcxeqoniopzbemhkezvadjblpgmyuwlkwilipuccuqfvyzxtoathpnprqphtsiqjlocrmupngjnuskvbzadwxtxchsutumbvidxauotploicaqxegkstdfkyqbmegjhzdrqsuvrspqzbesgzwelrlejlilqvybdjyflbcziqlncddoohurovyuhfhjoyrkxbrvsepxbsivtrahz");
        long end1 = System.nanoTime();
        System.out.println(abccba1 + "时间：" + (end1 - start1) / (1000 * 1000));
    }
}
